package com.lw.leetcode.linked.c;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 895. 最大频率栈
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/11 10:29
 */
public class FreqStack {


    public static void main(String[] args) {
        FreqStack test = new FreqStack();

        //输出：[null,null,null,null,null,null,null,5,7,5,4]
        test.push(5);
        test.push(7);
        test.push(5);
        test.push(7);
        test.push(4);
        test.push(5);

        System.out.println(test.pop());
        System.out.println(test.pop());
        System.out.println(test.pop());
        System.out.println(test.pop());
    }


    private Node st = new Node(-1);
    private Node end = new Node(-1);
    private Map<Integer, Item> map = new HashMap<>();
    private int index;

    public FreqStack() {
        st.next = end;
        end.pre = st;
    }

    public void push(int val) {
        Item item = map.get(val);
        if (item == null) {
            item = new Item(val);
            item.indexs.add(index);
            map.put(val, item);
            Node next = getNext(st, 0);
            next.list.add(item);
            item.parent = next;
        } else {
            Node parent = item.parent;
            item.indexs.add(index);
            Node next = getNext(parent);
            next.list.add(item);
            item.parent = next;
            parent.list.remove(item);
        }
        index++;
    }

    private Node getNext(Node no, int count) {
        Node next = no.next;
        if (next.count == count + 1) {
            return next;
        }
        Node node = new Node(count + 1);
        node.next = next;
        next.pre = node;
        node.pre = no;
        no.next = node;
        return node;
    }

    private Node getNext(Node no) {
        return getNext(no, no.count);
    }

    private Node getPre(Node no) {
        Node pre = no.pre;
        int count = no.count;
        if (count - 1 == pre.count) {
            return pre;
        }

        Node node = new Node(count - 1);
        node.next = no;
        no.pre = node;
        node.pre = pre;
        pre.next = node;
        return node;

    }

    public int pop() {

        Node pre = end.pre;

        List<Item> list = pre.list;
        int max = 0;
        int j = 0;
        for (int i = 0; i < list.size(); i++) {
            Item item = list.get(i);
            int t = item.indexs.get(item.indexs.size() - 1);
            if (t > max) {
                max = t;
                j = i;
            }
        }

        Item item = list.get(j);

        int size = item.indexs.size();

        pre.list.remove(j);
        if (size == 1) {
            item.parent = null;
            map.remove(item.value);
        } else {
            item.indexs.remove(size - 1);
            Node node = getPre(pre);
            node.list.add(item);
            item.parent = node;
        }
        if (pre.list.size() == 0) {
            Node pre1 = pre.pre;
            pre1.next = end;
            end.pre = pre1;
            pre.list = null;
            pre.next = null;
            pre.count = 0;
            pre.pre = null;
        }
        return item.value;
    }

    private static class Node {
        public Node(int count) {
            this.count = count;
        }

        private int count;

        private Node next;

        private Node pre;

        private List<Item> list = new ArrayList<>();

    }


    private static class Item {
        public Item(int value) {
            this.value = value;
        }

        private Node parent;

        private int value;

        private List<Integer> indexs = new ArrayList<>();

    }


}
